The following background description is provided to give context and understanding to the recited invention and is not meant to be limiting of the claims.
Computing Devices
Computing devices, such as those that are connected to form a network, are organized in layers. FIG. 1 is a diagram illustrating a computing device with its layers. There is a hardware layer 100, which includes the physical hardware components of the system, such as one or more processors (CPUs) 102, system memory 104, one or more a storage devices 106, and attached peripheral hardware. There is a software layer referred to as “user space” 160, which includes user software applications 162, 164, and 166, such as a text editors, email programs, and web browsers. Between the hardware layer and the user space layer, there is another software layer, the operating system kernel 130, (“the kernel”). The kernel acts as an interface between the computer hardware and the user applications, and includes the software processes that actually run the computer. The kernel is responsible for tasks, such as allocating the CPU and memory among the user application processes, and managing and coordinating input and output “I/O” requests from user applications. For example, the kernel processes messages that user applications send to and receive from other computing devices, so that the messages can be sent over the network hardware.
When a computing device is attached to a network, the hardware layer may also include one or more network interface controllers, (“NICs”), illustrated at 110 and 112 of FIG. 1. NICs are hardware controllers that allow the computing device to be attached to the network's physical media 202 and 204, and that send signals to and receive signals from other computing devices on the network. As used in this application, the physical media for a network includes physical structures, such as wires and fiber optical cables, and also wireless media such as radio waves. A computing device (complete with operating system running) with a NIC connected to a network is often referred to in the art as a “host.”
The kernel of a host includes a device driver for each NIC in the host, as illustrated at 132 and 134. Device drivers are kernel software modules that handle input and output “I/O” for specific hardware devices by translating the general I/O instructions of the operating system to specific instructions that the devices, such as a NIC, can understand. Thus, when a computing device sends and receives messages across the network through a particular NIC, the messages are processed by the device driver for the NIC. The kernel also includes a network interface for each NIC, illustrated at 136 and 138. A network interface includes a data structure and functions that define how a NIC device driver needs to present incoming data to the higher levels of the operating system, and how the higher levels of the operating system need to present data to the NIC device driver.
As will be explained in more detail below, when a user space application wants to send a message to another computing device, it forwards the message data and destination information to a networking subsystem in the kernel, illustrated at 140. The networking subsystem processes the message and presents it to the NIC device driver (132 or 134) through the associated network interface (136 or 138). From the device driver (132 or 134) it can be forwarded out of the computing device through the NIC (110 or 112). When a message is received at a NIC, it may be sent to the NIC device driver in the kernel, and presented to the networking subsystem by the network interface.
Computer Networks
Computer networks are also often organized into hardware and software layers. A physical network layer is created, i.e. the hardware layer. Then a software layer is defined for the physical layer. The software layer definition is basically a generalization of the hardware that can be understood by the software layers in the computing devices that may not be constructed from the same type of hardware. Physical networks and software layer definitions are well known in the art of computer science. An Ethernet Network is an example of hardware network, and Internet Protocol version 4, “IP” network, which is used in the Internet, is an example of the software layer definition of a network. To the extent that Ethernet Network protocols and IP are used herein, they are used as examples and are not meant to be limiting. In would be well understood in the relevant art how these examples could be generalized to other hardware networks and software layer network definitions.
FIG. 2A is a diagram illustrating an example of a hardware layer of a network. As is often the case, the network is made up of smaller networks, illustrated in FIG. 2A as Network 1 202 and Network 2 204. As shown in FIG. 2A, the hardware layer of the network includes a number of NICs 210, 212, 214, 216, and 218, attached to computing devices Host A 206, Host B 207, Host C 208, and Host D 209 respectively, (with Host C including both NIC 214 and 216). Additionally, the network layer includes the physical media 220 and 222 connecting the computing devices. Each NIC in the network is identified by a unique address referred to as a Media Access Control, (“MAC”) address. In FIG. 2A, NIC 210 has MAC Address 1, NIC 212 has MAC Address 2, NIC 214 has MAC address 3, NIC 214 has MAC Address 4, NIC 216 has MAC Address 5, and NIC 218 has MAC Address 5.
FIG. 2B is a diagram illustrating the software definition of the hardware network illustrated in FIG. 2A. As illustrated in FIGS. 2A and 2B, the software layer definition of a network is also broken into smaller networks, which often correspond to the smaller networks in the hardware layer. These smaller networks are often referred to as “subnets” in the software layer definition. Each subnet includes at least one computing device linked to the network by a physical medium. In FIGS. 2A and 2B, Subnet 1 252 corresponds to Hardware Network 1 202 and Subnet 2 254 corresponds to Hardware Network 2 204. The hosts on each subnet are typically able to send and receive communications directly to and from hosts on the same subnet. However, for a host (referred to as a “source”) to send a message to another host (referred to as a “destination”) on a different subnet, the sending host must transmit the message to a “router” or “gateway.” The term “router” will be used herein. A router is a host that is connected to more than one subnet, and can transmit a message from one subnet to another subnet. Host C 208 in FIG. 2B is a router because it is connected to both Subnet 1 252 and Subnet 2 254.
Each host in a network generally has a unique software layer address for each subnet on the host, and as is well known in the art, each software layer addresses in the host indicates a subnet that the host is part of. In an IP network, this address is referred to as the “IP address,” which is used in this description for clarity. One of skill in the art could generalize the description below to other network software layer protocols. As illustrated in FIG. 2B, Host C has two IP Addresses, (IP Address 3 and IP Address 4) because it is connected to two subnets.
Processing a Message Sent from a Source to a Destination
As explained above, when a user space application (such as an email program) wants to send a message (such as an email), the user space application forwards the message data and destination information to the kernel, where it is processed by the networking subsystem illustrated in FIG. 1 at 140. The term “networking subsystem” is used herein as a broad term to describe the components of the kernel that process messages sent by user space applications before they are forwarded to the network interface, and that process messages from the network interfaces before they are sent to user space applications. A non-limiting example of a networking subsystem is the IP subsystem used to process messages in IP networks.
Because messages sent between hosts are often large, the networking subsystem breaks messages into pieces, and sends the messages in “packets.” A packet is a bit stream that includes a piece of the message data and information about itself. Packets are defined by a protocol that dictates the structure of the packet, i.e. which bits in the packet contain what type of information. FIG. 3A is a diagram illustrating an example of a packet. An IP packet is shown for illustration purposes. The packet illustrated in FIG. 3A is from a message being sent from Host A 206 to Host D 209 in FIG. 2B. The first set of bits in the packet, which is illustrated at 301, is the start of the header, and includes information such as the protocol of the packet and other information about the packet. The next set of bits, which is illustrated at 302, includes the address of the message source, i.e. the IP Address of Host A, IP Address 1. The next group of bits 304 includes the address of the destination, i.e. the IP Address of Host D, IP Address 5. The bits including the rest of the header are illustrated at 306, and the bits including the actual message data are illustrated at 308.
As explained above, if a packet is sent to a destination in the source's subnet, it may be sent directly to the destination. However, if a packet is sent to a computer outside the source's subnet, it is sent to a router in the source's subnet, such as Host C at 208 of FIG. 2A. Because there may be more than one router on a single subnet, the networking subsystem must determine the appropriate router, by “routing” the packet. To route packets, the networking subsystem looks up the appropriate router for the destination in a routing table, illustrated at 142 in FIG. 1. FIG. 4A is a diagram illustrating a routing table for Host A 206 or Host B 207 of FIG. 2B. A routing table includes two essential columns, the destination's subnet 402, and a software layer address for the appropriate router, or “gateway,” 404. As illustrated in FIG. 4A at 403 and 405, any packet from Host A or Host B with a destination on Subnet 2 is sent to IP Address 3, i.e. Host C's software layer address on Subnet 1.
Once the software layer address of the router is found in the routing table; however, the networking subsystem will not place that address inside the packet because the destination address in the packet needs to be the actual address for the destination. Additionally, the hardware, such as the network hardware and the media that physically connect the computing devices, does not understand the software layer definitions of the network, such as the software layer addresses and packet construction. Therefore, rather than just sending packets across a hardware network, hosts send bit streams that encapsulate the data for the packet, and include information that the hardware layer understands. Although the name for such bit streams may vary depending on the type of hardware network, the term “frames,” will be used herein for simplification. Like a packet, frames are defined by a protocol that dictates their structure, i.e. which bits in the frame contain what type of information. FIG. 3B is a diagram illustrating a frame for sending the packet in FIG. 3A between Host A 206 and Host D 209 in FIGS. 2A and 2B. An Ethernet packet is shown in FIG. 3B for illustrative purposes. As illustrated at 310, the payload of the frame includes the packet shown in 3A.
As illustrated at 311 and 312 in FIG. 3B, the frame includes the hardware address, e.g. the MAC address of the source or destination, rather than the software layer address. Because the source is Host A, the Source MAC 311 is the address of the NIC 210 in FIG. 2A. The networking subsystem must determine the MAC address for the destination from the software layer address of the router. This is done using an address resolution system that bridges the hardware and software layer addresses. Address resolution systems are well known in the art. A non-limiting example of an address resolution system is the Address Resolution Protocol (“ARP Protocol”) used in Ethernet and IP. Address resolution systems use a MAC table illustrated at 144 of FIG. 1, which may also be referred to as an “ARP Table” in Ethernet and IP. A MAC table for Host A is illustrated in FIG. 4B. The MAC table consists of two columns: an IP address 406 and a MAC address 408. As illustrated at 410 and 412, the IP Address 2 for Host B corresponds to MAC Address 2, the hardware address of NIC 2. As illustrated at 414 and 416, the IP Address 3 of Host C (the address for Subnet 1) is associated with MAC Address 3, the hardware address for NIC 214. Thus, in FIG. 3B at 312 the Destination MAC for the frame forwarding the packet to the router Host C is MAC Address 3.
MAC tables and routing tables need occasional updates. For example, the MAC table may not include a destination address for a particular outgoing frame. In such a case, the address resolution system may query other hosts in the network, and update the MAC table when the answer to the query arrives. Additionally, the MAC table may be updated manually. Other methods for updating the MAC table are well known in the art.
Methods for updating routing tables are also well known in the art. For example, a user may update the routing table manually. Additionally, the operating system may run a service implementing a dynamic routing protocol, which updates the routing tables in response to requests from the network. Other methods for updating the routing table are also well known in the art.
Routing tables and MAC tables are examples of forwarding information databases, i.e. the databases used by the networking subsystem to determine the necessary information for forwarding packets. Other examples of forwarding information database include: neighbor tables, IP tables, and Access Control Lists (“ACL”) tables. As would be understood by one of skill in the art, these examples are not meant to be limiting.
Once the networking subsystem has determined the Destination MAC address for an outgoing packet, it can finish constructing the frame. The networking subsystem then forwards the complete frame to the next level in the kernel, the network interface (FIG. 1 at 136 and 138) associated with the NIC that has the Source MAC Address. As explained above, the network interface is associated with a particular NIC, and includes a data structure and functions that present frames that are in a standard format from the networking subsystem to the particular NIC device driver. Network interfaces also present incoming frames from a particular NIC device driver to the networking subsystem in a standard format. Each type of NIC requires a different device driver, and therefore a different implementation of the network interface, even though all NICs perform the same basic task, i.e. sending and receiving frames. Each attached NIC has its own network interface.
From the network interface, the frame is forwarded to the NIC device driver to send to the NIC, where it will be transmitted across the network to the Destination MAC. For example, the frame in FIG. 3B is forwarded to NIC 214 on Host C 208 of FIG. 2A, which is also illustrated by NIC 110 of FIG. 1. The frame may then be processed by the networking subsystem at the destination. In such case, the frame is received at the device driver in the host for that NIC. For example, in FIG. 1 the frame would be sent to device driver 132 and then forwarded to network interface 136 where it could be presented to the networking subsystem 140 for processing. The networking subsystem processes the frame by looking at the software layer destination address in the packet, and if the host is not the destination address, constructing an updated frame. The networking subsystem constructs an updated frame in a manner similar to constructing a frame as described above. FIG. 3C is a diagram illustrating an updated frame constructed at Host C 208 of FIGS. 2A and 2B for the packet being sent from Host A 206 to Host D 209. Because Host D is on the same subnet as NIC 216 in Host C, the Source MAC 350 is NIC 216's MAC address, i.e. MAC Address 4. The Destination MAC 352 is the address for the NIC in Host D, i.e. MAC Address 5. The payload 360 is the same packet 300 as in FIGS. 2A and 2B. The updated frame is then forwarded to the network interface 138 associated with NIC 216, which is also illustrated as NIC 112 in FIG. 1. The updated frame is then forwarded to NIC device driver 134, sent to NIC 112, and sent to Host D over the network.
In order to accelerate the processing and forwarding of frames, an attached hardware switch device may be programmed to perform some networking tasks without involving the kernel. However, there are certain networking tasks that may be too complex to implement in the hardware switch. Therefore, it would be useful to have systems and methods for efficiently handing interactions between the programmed switch device and the operating system. It would also be useful to have systems and methods for synchronizing networking data between the operating system and the ASIC switch device.